package LeetcodeTest_eighteen;
//上生下降字符串
public class sortString
{
    public static void main(String[] args)
    {
        System.out.println(Solution.sortString("leetcode"));
    }
}
class Solution
{
    public static String sortString(String s)
    {
        int i;
        StringBuilder answer=new StringBuilder();
        boolean flag=true;
        int numOfLetter[]=new int[26];
        for(i=0;i<s.length();i++)
        {
            numOfLetter[s.charAt(i)-'a']++;    //桶排序，记录每个字符出现次数
        }
        while(flag)       //当s中字符都被选择过后退出
        {
            i=0;
            //步骤1，2，3；i从小到大，始终会选择剩余未选字符里面最小的那个
            while (i < 26)
            {
                if (numOfLetter[i] != 0)
                {
                    answer.append((char)('a' + i));
                    numOfLetter[i]--;
                }
                i++;
            }
            i = 25;
            //步骤4，5，6；i从大到小，始终会选择剩余未选字符里面最大的那个
            while (i >= 0)
            {
                if (numOfLetter[i] != 0)
                {
                    answer.append((char)('a' + i));
                    numOfLetter[i]--;
                }
                i--;
            }
            //对s中字符是否都被选择过进行判断
            for (i=0;i<numOfLetter.length;i++)
            {
                if (numOfLetter[i] != 0)
                    break;
            }
            if(i>=numOfLetter.length)
                flag=false;
        }
        return answer.toString();
    }
}